#include<bits/stdc++.h>
#define For(i,j,k) for(int i=(j);i<=(k);++i)
#define ForDown(i,j,k) for(int i=(j);i>=(k);--i)
#define Debug(fmt, args...) fprintf(stderr,"(func %s, line #%d): " fmt,__func__,__LINE__,##args),fflush(stderr)
#define debug(fmt, args...) fprintf(stderr,fmt,##args),fflush(stderr)
#define within :
#define LJY main
using namespace std;
typedef long long ll;
const int N=105;
inline int read(){
  char ch=getchar();int x=0,f=1;
  while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
  while(ch>='0'&&ch<='9')
    x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
  return x*f;
}
int n,m,x[N],y[N];
bool vis[1<<10];
vector<pair<int,int> >Edge;
ll Mx,cnt=0;
int g[N][N];
void solve(){
  ll ans=0;
  memset(g,0x3f,sizeof(g));
  For(i,1,n) g[i][i]=0;
  for(auto [x,y] within Edge) g[x][y]=g[y][x]=1;
  For(k,1,n) For(i,1,n) For(j,1,n) g[i][j]=min(g[i][j],g[i][k]+g[k][j]);
  For(i,1,m) ans+=g[x[i]][y[i]];ans=-ans;
  if(ans>Mx) Mx=ans,cnt=1;
  else if(ans==Mx) cnt++;
}
void dfs(int x,int y,int cnt){
  if(cnt>=m) return;
  if(x>=n){
    if(cnt!=m-1) return;
    return solve();
  }
  if(y>n) return dfs(x+1,x+2,cnt);
  dfs(x,y+1,cnt);
  Edge.emplace_back(x,y);
  dfs(x,y+1,cnt+1);
  Edge.pop_back();
}
void ljy1(){
  n=read(),m=read();Mx=-1e18;cnt=0;
  For(i,1,m) x[i]=read(),y[i]=read();
  dfs(1,2,0);
  printf("%d %d\n",Mx,cnt);
}
void ljy2(){
  int n=read(),m=read();
  For(i,1,m) read(),read();
  printf("%d %d\n",-2*(n-1),0);
}
signed LJY(){
  freopen("oi.in","r",stdin);
  freopen("oi.out","w",stdout);
  int c=read(),T=read();
  while(T--){
    if(c>=1&&c<=2) ljy1();
    else ljy2();
  }
  return 0;
}